COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00012 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a101.tex[106,phy] \today\hfill}

\font\rmn=cmr9

\bigskip
\line{{\bf Case Study: Record Breakers} [Assignment]\hfil}
\smallskip
\line{This Could Be the Start of Something Big\hfil}

I want to design a program which reads an integer $N$, followed by a list of
$N$~numbers. The program must print the first number, the last number, and
the length, of the longest consecutive run of increasing numbers. That is,
the program can help me say fascinating things like ``The temperature rose
steadily, from 28 to~103, for 19~consecutive days. That's still a record.''

To prepare for programming the above problem, think about it this way.
If I were watching the consecutive data go by on a television screen,
and recording information on a very small blackboard, what information
would I keep that would guarantee that I could answer the question the
program is designed to answer?

I must record the starting value, final value, and length of the longest
run I have seen so far, because the numbers I have not yet seen might
steadily decrease. That is not enough to record, though; if I am currently
in the middle of a run which will eventually be seen to be the longest so
far, I will need to know its starting value and how long it was, so I
need to keep the starting value and length so far; even if the number I
am currently looking at is smaller than the one before, it might be the
start of a long run. I also need to remember the last number of the 
current run, to see if the next number continues it.
(Drill: Check that no more information is needed.)
The main iteration is then:

\smallskip
{\obeylines\obeyspaces\let =\ \tt
        FOR I:= 1 TO N DO
            BEGIN
            READ(NEWDAT);
            IF NEWDAT>LAST THEN
                BEGIN
                LAST:=NEWDAT;
                LENGTH:=LENGTH + 1
                END
            ELSE
                BEGIN
                FIRST:=NEWDAT;
                LAST:=NEWDAT
                LENGTH:=1
                END;
            IF LENGTH>OLDLENGTH THEN
                OLDFIRST:=FIRST;
                OLDLENGTH:=LENGTH;
                OLDLAST:=LAST
            END.
}


After the first datum is read, we want to have {\tt FIRST}, {\tt LAST}, 
{\tt OLDFIRST} and
{\tt OLDLAST} equal to that datum, and {\tt LENGTH} and {\tt OLDLENGTH} 
equal to~1. 
The main iteration will do this if I~initialize {\tt LAST} to the largest 
possible number, and {\tt OLDLENGTH} to~0.

The program then is

\medskip
{\obeylines\obeyspaces\let =\ \tt
        LAST:=MAXINT;
        OLDLENGTH:=0
        (* Insert main iteration here *)
        WRITE(OLDLENGTH,OLDFIRST,OLDLAST)
}

The variable {\tt OLDLENGTH} in the program above is an example of what I~call a
{\it ratchet\/}; it can only move one way because it is changed only to a value
known to be larger than its previous value. If initialized to a small
enough value, a ratchet keeps track of the largest value ever presented
to it. Often, as in the example, it is accompanied by other variables
that record information about the context in which the ratchet was last
changed.

{\rmn
{\narrower\smallskip\noindent
{\bf Exercise:} Assume $f(x)$ is a function that is negative in some finite
interval that is a subset of $0≤x≤1$. Design an algorithm to find an~$x$
for which $f(x)$ is negative; it should work in principle even if the
interval is extremely small.

Demonstrate your algorithm by writing a program that makes

{\obeylines\obeyspaces\let =\ \tt
        f(x)=COS(505.60213*x)+COS(386.16855*x)+1.999
}

\noindent
negative.

I suggest debugging your program using a function for which you know the answer,
like

{\obeylines\obeyspaces\let =\ \tt
        f(x)=SQR(x-0.29)-0.001
}

This program requires no calculus. If the body of your program is more than
thirty lines, you are doing something the hard way.
\smallskip}
}

\bigskip
\line{\copyright 1984 Robert W. Floyd; 
First draft (not published) March 15, 1984\hfil}
%revised: Date; subsequently revised.\hfill}

\vfill\eject

\line{\bf Solution.\hfill}

\smallskip
{\obeylines\obeyspaces\let =\ \tt
program LongLoop (output);
(*******************************************************************
    R. Floyd, October 18, 1984, File name MAKENG.PGO
    This program tries to find a value of X for which the function
    F(X) is negative.  F(X) is guaranteed to be continuous, and
    negative at some X, 0 <= X <= 1. The algorithm works by testing 
    the following values of X:

        X=1/2
        X=1/4,3/4
        X=1/8,3/8,5/8,7/8

    and so on. If a good X is not found by moving through the
    interval 0<X<1 with a particular increment for X (inner loop),
    the increment is halved for the next search. For testing use
    FVALUE:=SQR(X-0.375)-0.01.
*******************************************************************)
    var Unfinished: boolean;
        I, Power: integer;
        X, FValue: real;
    begin
        (* Initialize *)
        Unfinished := true;
        Power:=2;
        while Unfinished do
        begin
            I:=1;
            while (I<Power) and Unfinished do
            begin
                X:=I/Power;
                FValue:=COS(505.60213*X)+COS(386.16855*X)+1.999;
                if FValue<0 then Unfinished:=false
                else I:=I+2;
            end;
            Power:=2*Power;
        end;
        writeln('At X= ',X,' the value of F(X)= ',FValue);
     end. (* LongLoop *)
     OUTPUT:
     At X=7.890625E-01 the value of F(X)=-2.593696E-04
}


\medskip
\parindent0pt
\copyright 1984 Robert W. Floyd. First draft October 18, 1984.

\bye